package sort.basic_sort;

import java.util.Arrays;

/**
 * @author dx
 * @version 1.0
 * @date 2022/4/16 11:30
 * @description:  在未排序序列种找到最小(大)元素，存放到未排序序列的起始位置，
 *
 */
public class select_sort {

    public static void selectionSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            int min = i;
            for(int j = i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            if(min != i){
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i]  = temp;
                System.out.println("SOrting: "+ Arrays.toString(arr));
            }
        }
    }
}
/*
冒泡排序和选择排序的区别：https://zhuanlan.zhihu.com/p/137220037
冒泡排序：从左往右，两两比较大小，左边的大就交换位置，循环往复，把较大的放后面
选择排序：从第一数开始，与后面所有的数想比较，找出最小的数，放在第一个位置，依此类推，每一轮确定一个相对于这一轮最小的数

区别：
冒泡排序是左右两个数相比较，而选择排序是用后面的数和每一轮的第一个数相比较
冒泡排序每轮交换的次数比较多，而选择排序每轮只交换一次

时间效率上看，选择排序优于冒泡排序



这两个算法思想上是一样的，确实容易混淆，每一轮冒泡从结果看，等价于从待排序序列中选择一个最大的数放在特定位置，
这与选择排序是一样的。不同之处在于，选择排序指交换两个元素时并不影响其他元素的相邻位置，而冒泡排序在交换过程中会改变其他元素的相邻位置。
选择排序是与输入无关的，每次选择都要遍历待排序序列，时间复杂度固定约为N^2/2，而冒泡排序与输入有关，如果一轮遍历没有元素交换，就可以断定序列已经有序，
其时间复杂度平最好时可以达到N，最坏约N^2/2，平均时间复杂度虽然增长量级也是N^2/2，但实际是要优于选择排序的，具体取决于待排序序列的部分有序程度。
 */